//445. 两数相加 II

//给你两个 非空 链表来代表两个非负整数。
//数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
//你可以假设除了数字 0 之外，这两个数字都不会以零开头。

#include <stdio.h>
struct ListNode 
{
    int val;
    struct ListNode *next;
  };

//反转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* curr = head;

    while(curr)
    {
        struct ListNode* next = curr->next;
        curr->next = newhead;
        newhead = curr;
        curr = next;
    }
    return newhead;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
    // 反转链表，使低位在前（个位、十位、百位...）
    l1 = reverseList(l1);
    l2 = reverseList(l2);

    // 创建哑节点简化操作，dummy始终指向头节点
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = NULL;  // 初始化
    struct ListNode* p = dummy;  // 用于构建结果链表的指针

    int carry = 0;  // 进位值

    while(l1 != NULL || l2 != NULL || carry != 0)
    {
        int sum = carry;  // 先加上进位
        
        // 累加l1当前节点的值
        if(l1 != NULL)
        {
            sum += l1->val;
            l1 = l1->next;  // 移动到l1的下一个节点
        }
        
        // 累加l2当前节点的值
        if(l2 != NULL)
        {
            sum += l2->val;
            l2 = l2->next;  // 移动到l2的下一个节点
        }
        
        // 计算当前位的值和新的进位
        p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        p->next->val = sum % 10;  // 当前位的值（对10取模）
        carry = sum / 10;  // 更新进位（整除10）
        
        // 移动到下一个节点
        p = p->next;
        p->next = NULL;
    }

    // 结果链表的有效部分是newlist->next（跳过哑节点）
    struct ListNode* temp = dummy->next;
    free(dummy);  // 释放哑节点
    
    // 反转结果链表，恢复正确的数字顺序
    struct ListNode* result = reverseList(temp);
    return result;
}
    